package com.awakening.sorting.basic;

import com.awakening.sorting.util.SortTestHelper;

/**
 * 改进插入排序法
 * @Author:AwakeningCode
 * @Date: Created in 11:54 2018\1\17 0017
 */
public class InsertionSortAdvance {

    //InsertionSortAdvance算法不允许产生任何实例
    private InsertionSortAdvance(){}

    //对arr[l...r]的区间使用InsertionSort排序
    public static void sort(Comparable[] arr,int l,int r){
        assert l >= 0 && l <= r && r < arr.length;

        for (int i=l+1;i<=r;i++){
            Comparable e =arr[i];
            int j = i;
            for( ; j > 0 && arr[j-1].compareTo(e) >0 ;j--){
                arr[j] = arr[j-1];
            }
            arr[j] = e;
        }
    }

    public static void sort(Comparable[] arr){
        int n = arr.length;
        for(int i = 0;i < n;i++){
            // 寻找元素arr[i]合适的插入位置

            // 写法1
//            for( int j = i ; j > 0 ; j -- )
//                if( arr[j].compareTo( arr[j-1] ) < 0 )
//                    swap( arr, j , j-1 );
//                else
//                    break;

            // 写法2
//            for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--)
//                swap(arr, j, j-1);

            // 写法3
            Comparable e = arr[i];
            int j = i;
            for ( ; j>0&& arr[j-1].compareTo(e)>0;j--){
                arr[j] = arr[j-1];
            }
            arr[j] = e;
        }
    }

    // 测试InsertionSort
    public static void main(String[] args) {

        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("com.awakening.sorting.basic.InsertionSortAdvance", arr);

        return;
    }

}
